package com.链表.练习题;

public class Leetcode234 {
    /**
     * 回文链表
     *
     * 给你一个单链表的头节点 head ，
     * 请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
     *
     * 输入：head = [1,2,2,1]
     * 输出：true
     */
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) return true;
        ListNode p1 = head;
        ListNode p2 = head;
        ListNode n1 = null;
        ListNode o1 = head;
        while (p2 != null && p2.next != null){
            p1 = p1.next;
            p2 = p2.next.next;

            o1.next = n1;
            n1 = o1;
            o1 = p1;

        }
        if (p2 != null) { // 节点数为奇数
            p1 = p1.next;
        }
        // 同步比较新头和后半部分
        while (n1 != null) {
            if (n1.val != p1.val) {
                return false;
            }
            p1 = p1.next;
            n1 = n1.next;
        }
        return true;
    }
}
